package pro.softzhang.algo.lc700;

import pro.softzhang.algo.flag.knowledge.KGraph;

import java.util.*;

/**
 *
 */
@KGraph
public class LC752_OpenTheLock {
    public static void main(String[] args) {

    }

    static class Solution {
        public int openLock(String[] deadends, String target) {
            Set<String> dead = new HashSet<>(Arrays.asList(deadends));
            Set<String> visited = new HashSet<>();
            String init = "0000";
            if(dead.contains(init) || dead.contains(target)) {
                return -1;
            }

            Queue<String> q1 = new LinkedList<>(), q2 = new LinkedList<>();
            int steps = 0;
            q1.offer(init);
            visited.add(init);

            while (!q1.isEmpty()) {
                String current = q1.remove();
                if(target.equals(current)) {
                    return steps;
                }

                List<String> nexts = getNeighbors(current);
                for (String next : nexts) {
                    if(!dead.contains(next) && !visited.contains(next)) {
                        q2.add(next);
                        visited.add(next);
                    }
                }

                if(q1.isEmpty()) {
                    steps++;
                    q1 = q2;
                    q2 = new LinkedList<>();
                }
            }

            return -1;
        }

        private List<String> getNeighbors(String current) {
            List<String> nexts = new LinkedList<>();
            for (int i = 0; i < current.length(); i++) {
                char ch = current.charAt(i);
                char newCh = ch == '0' ? '9' : (char) (ch - 1);
                StringBuilder sb = new StringBuilder(current);
                sb.setCharAt(i, newCh);
                nexts.add(sb.toString());

                newCh = ch == '9' ? '0' : (char) (ch + 1);
                sb.setCharAt(i, newCh);
                nexts.add(sb.toString());
            }
            return nexts;
        }
    }
}
